//
// Created by 123 on 2024/3/20.
//
#include <iostream>
#include <stack>

using namespace std;


/**
 *
 * 课本定义方法
 *

#define MaxVertexNum 100
//顶点对应数据类型
typedef char VertexType;
//边对应数据类型
typedef int EdgeType;
typedef struct {
//    顶点表
    VertexType vex[MaxVertexNum];
//    边表
    EdgeType edge[MaxVertexNum][MaxVertexNum];
//    图的当前顶点数和边数
    int vexnum;
    int arcnum;
};


 *
 */

#define MaxSize 8
int grap[MaxSize][MaxSize] = {
        {0, 1, 0, 0, 1, 0, 0, 0},
        {1, 0, 0, 0, 0, 1, 0, 0},
        {0, 0, 0, 1, 0, 1, 1, 0},
        {0, 0, 1, 0, 0, 0, 1, 1},
        {1, 0, 0, 0, 0, 0, 0, 0},
        {0, 1, 1, 0, 0, 0, 1, 0},
        {0, 0, 1, 1, 0, 1, 0, 1},
        {0, 0, 0, 1, 0, 0, 1, 0},
};
int d[8] = {9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999};

bool isVisited[MaxSize] = {false, false, false, false, false, false, false, false};
//    1  {0, 1, 0, 0, 1, 0, 0, 0},
//    2  {1, 0, 0, 0, 0, 1, 0, 0},
//    3  {0, 0, 0, 1, 0, 1, 1, 0},
//    4  {0, 0, 1, 0, 0, 0, 1, 1},
//    5  {1, 0, 0, 0, 0, 0, 0, 0},
//    6  {0, 1, 1, 0, 0, 0, 1, 0},
//    7  {0, 0, 1, 1, 0, 1, 0, 1},
//    8  {0, 0, 0, 1, 0, 0, 1, 0},


//深度优先 栈实现
void dfs_stack(int vex);

// 深度优先 递归实现
void dfs_recursion(int f,int vex) ;


void dfs(int vex) {
    d[vex-1]=-1;
    dfs_recursion(vex-1,vex - 1);
}


int main() {
    dfs_stack(2);
//    dfs(2);


    cout<<"-----------------------------------------"<<endl;
    cout<<" 2到各个节点的距离"<<endl;
    for (int i = 0; i < 8; ++i) {
        cout << i+1 << ": " << d[i] << "    ";
    }

}

void dfs_recursion(int f,int vex) {
    cout << vex + 1 << "   ";
    d[vex]=d[f]+1;
    isVisited[vex] = true;
    for (int i = 0; i < MaxSize; ++i) {
        if (grap[vex][i] == 1 && !isVisited[i]) {
            dfs_recursion(vex,i);
        }
    }
}

void dfs_stack(int vex) {
    cout << vex << "   ";

//    最短路径问题
    d[vex-1]=0;
    isVisited[vex - 1] = true;
    stack<int> sta;
    sta.push(vex - 1);

    while (!sta.empty()) {
        int cur = sta.top();
        sta.pop();
        for (int i = 0; i < MaxSize; ++i) {
            if (grap[cur][i] == 1 && !isVisited[i]) {
                //加入cur，方便回溯
                sta.push(cur);
                sta.push(i);
                isVisited[i] = true;

                d[i]=d[cur]+1;// 最短路径问题
                cout << i + 1 << "   ";
                break;//由于是深度优先遍历，所以只要找到该深度的且之前未被找到的点即可
            }
        }
    }
    cout << endl;
}
